package Map;
import java.util.*;

public class Exercise {
    public static void main(String[] args) {
        int[] array = {1,5,2,5,6,4,3,2};
        repeatNumber(array);
        System.out.println();
        System.out.println(" 前k个高频单词: ");
        String[] words = {"i", "love", "leetcode", "i", "love", "coding"};
        List<String> list = topKFrequent(words,3);
        System.out.println(list);
    }
    public static void repeatNumber(int[] array) {
        Map<Integer,Integer> map = new HashMap<>();
        for (int x : array) {
            if(map.get(x) == null) {                 //如果一开始没有这个key，那么就把这个key插入，又因为是第一次插入所以value是1
                map.put(x,1);
            }else {                                 //如果这个key存在，那么再出现这个key表示出现的次数加1，则val = val+1
                int val = map.get(x);
                map.put(x,val+1);
            }
        }
        for (Map.Entry<Integer,Integer> entry: map.entrySet()) {
            if(entry.getValue() > 1) {
                System.out.print(" key: "+entry.getKey()+" value: "+entry.getValue());
            }
        }
    }
    public static List<String> topKFrequent(String[] words, int k) {
        List<String> list = new ArrayList<>();
        Map<String,Integer> map = new HashMap<>();
        for (int i = 0;i < words.length;i++) {
            if(map.get(words[i]) == null) {
                map.put(words[i],1);
            }else {
                map.put(words[i],map.get(words[i])+1);
            }
        }
        //建一个小根堆
        Queue<Map.Entry<String,Integer>> minHeap = new PriorityQueue<>(k,new Comparator<Map.Entry<String,Integer>>() {
            @Override
            public int compare(Map.Entry<String,Integer> o1,Map.Entry<String,Integer> o2) {
                //把对堆顶元素放入list中的时候会出现一个问题，如果根据value比较那么当有两个value相同的key时，就不会比较
                //所以就需要在进行比较，当poll()元素的时候，调整小根堆的元素，将key值大的先取出
                if(o1.getValue().compareTo(o2.getValue()) == 0) {
                    return o2.getKey().compareTo(o1.getKey());
                }
                //这边是根据出现的频率进行比较
                return o1.getValue().compareTo(o2.getValue());
            }
        });
        for (Map.Entry<String,Integer> e : map.entrySet()) {
            //先把前k个单词放入到小根堆中，在进行比较
            if (minHeap.size() < k) {
                minHeap.offer(e);
            }else {
                //到这里开始进行比较
                if(e.getValue().compareTo(minHeap.peek().getValue()) > 0) {
                    minHeap.poll();
                    minHeap.offer(e);
                }else {
                    //这边就需要进行字典顺序的比较
                    if(e.getValue().compareTo(minHeap.peek().getValue()) == 0) {
                        if(e.getKey().compareTo(minHeap.peek().getKey()) < 0) {
                            minHeap.poll();
                            minHeap.offer(e);
                        }
                    }
                }
            }
        }
        while(!minHeap.isEmpty()) {
            list.add(0,minHeap.poll().getKey());
        }
        return list;
    }
}
